package com.jake.data_structure_learning.sort;

/**
 * copyright (C), 2021, 武汉德辞信息技术有限公司
 * 排序算法
 *
 * @author WangXiang
 * @version 1.0.0
 * @create 2021/6/7 16:14
 * @description <author>                <time>                  <version>
 * WangXiang               2021/6/7 16:14            1.0.0
 */
public class Sort {

    /**
     * @param nums
     * @return void
     * @description 冒泡排序
     * @date 2021/6/7 16:14
     * @author WangXiang
     */
    public void bubbleSort(int[] nums) {
        if (nums == null || nums.length < 1) {
            return;
        }
        int temp;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                // 交换
                if (nums[i] > nums[j]) {
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }

    /**
     * @param nums
     * @return void
     * @description 选择排序
     * @date 2021/6/7 16:28
     * @author WangXiang
     */
    public void selectSort(int[] nums) {
        if (nums == null || nums.length < 1) {
            return;
        }

        int index = 0;
        int temp;
        for (int i = 0; i < nums.length - 1; i++) {
            index = i;
            // 第一次 第一个数字和后面所有的比较 找出最大的数字 下表记 index  和第一个交换
            // 第二次 第二个数据执行上面的操作
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > nums[index]) {
                    index = j;
                }
            }
            if (index != i) {
                temp = nums[i];
                nums[i] = nums[index];
                nums[index] = temp;
            }
        }
    }

    /**
     * @param nums
     * @return void
     * @description 插入排序  1 3 5 6 4
     * @date 2021/6/7 16:38
     * @author WangXiang
     */
    public void insertSort(int[] nums) {
        if (nums == null || nums.length < 1) {
            return;
        }

        int temp;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] < nums[j]) {
                    temp = nums[i];
                    System.arraycopy(nums, j, nums, j + 1, i - j);
                    nums[j] = temp;
                }
            }
        }
    }

    /**
     * @param nums
     * @return void
     * @description 快速排序
     * 快速排序原理是首先要找到一个中枢，把小于中枢的值放到他前面，大于中枢的值放到
     * 他的右边，然后再以此方法对这两部分数据分别进行快速排序。先看一下代码
     * @date 2021/6/7 17:40
     * @author WangXiang
     */
    public void quickSort(int[] nums) {
        if (nums == null || nums.length < 1) {
            return;
        }
        this.quickSort(nums, 0, nums.length - 1);
    }

    public void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int key = nums[start];
            int index = start;
            int temp;
            for (int i = start + 1; i <= end; i++) {
                if (nums[i] < key) {
                    temp = nums[i];
                    nums[i] = nums[index];
                    nums[index] = temp;
                    index++;
                }
            }

            this.quickSort(nums, start, index);
            this.quickSort(nums, index + 1, end);
        }
    }

    /**
     * @param nums
     * @return void
     * @description 归并排序
     * @date 2021/6/9 15:13
     * @author WangXiang
     */
    public void mergeSort(int[] nums) {
        mergeSort(nums, 0, nums.length-1);
    }

    public void mergeSort(int[] nums, int left, int right) {
        if (left < right) {
            int center = (right + left) / 2;
            mergeSort(nums, left, center);
            mergeSort(nums, center + 1, right);
            merge(nums, left, center, right);
        }
    }

    public void merge(int[] nums, int left, int center, int right) {
        int _left = left;
        int _right = center+1;
        int index = left;

        int[] temp = new int[nums.length];
        while (_left <= center && _right <= right) {
            if (nums[_left] <= nums[_right]) {
                temp[index++] = nums[_left++];
            } else {
                temp[index++] = nums[_right++];
            }
        }

        while (_left <= center) {
            temp[index++] = nums[_left++];
        }

        while (_right <= right) {
            temp[index++] = nums[_right++];
        }

        for (int i = left; i <=right; i++) {
            nums[i] = temp[i];
        }
    }

}
